﻿<?php

// main.php
//
// includes engine for creating image with shortest path

// notes:
//
// consider caching keyNodes... what about with various options...
//		(maybe cache the always un/blocked in a text file -- would this even be faster?)
//

main();

//main function
function main()
{
	global $drawBigImage,		$initTime,$mapTime,$keyNodesTime,$pathTime,$subTime,$neighborsTime,$lowFTime,$distanceBetweenTime,$collapseTime,$outputTime;
	
		$startTime=microtime(true);
		$initTime=0;
		$mapTime=0;
		$keyNodesTime=0;
		$pathTime=0;
		$subTime=0;
		$neighborsTime=0;
		$lowFTime=0;
		$distanceBetweenTime=0;
		$outputTime=0;
	
	//gets arguments & loads image
	init();
	
	//if this path has already been generated
	if(isPathCached())
	{
		retrieveOutput();
		echo("\n<br><br>\nretrieved from cache!<br>\n<br>\n");
	}
	//[not cached] finds shortest path (if a path exists)
	else if(findShortestPath())
	{
		//generates the image and JSON
		generateOutput();
	}
	else
	{
		echo('{"distance":"-1"}');//indicates error
		//echo("no path exists between start and end");
	}
	
		//debugging output
		echo("\n<br>\n<br>\n<br>\n<br>\n<pre>");
		echo("total time: ".(microtime(true)-$startTime)."\n");
		echo("\ninit() time: ".$initTime."\n");
		echo("    map[][] time: ".$mapTime."\n");
		echo("\nfindShortestPath() time: ".$pathTime."\n");
		echo("    low F time: ".$lowFTime."\n");
		echo("    sub-path time: ".$subTime."\n");
		echo("        key nodes time: ".$keyNodesTime."\n");
		echo("        neighbors time: ".$neighborsTime."\n");
		echo("        distance btwn time: ".$distanceBetweenTime."\n");
		echo("    collapse time: ".$collapseTime."\n");
		echo("\ngenerateOutput() time: ".$outputTime."\n");
		echo("</pre><br>\n");
	
}

//gets arguments, loads image pixel-array
function init()
{
	global $startx,$starty,$endx,$endy,		$initTime;
		
		$startTime=microtime(true);
	
	//get start, end, and options
	getArguments();
	
	//make 2-D array with which pixels are white or black
	makeArray();
	
	//if start is placed on blocked location
	if(isBlocked($startx,$starty))
	{
		//move to closest unblocked location
		list($startx,$starty)=movePointToUnblocked($startx,$starty);
		//echo("start: $startx , $starty\n");
	}
	
	//if end is placed on blocked location
	if(isBlocked($endx,$endy))
	{
		//move to closest unblocked location
		list($endx,$endy)=movePointToUnblocked($endx,$endy);
		//echo("end: $endx , $endy\n");
	}
	
		$initTime=microtime(true)-$startTime;
}

//retrieves start/finish coordinates
//and any options
function getArguments()
{
	global $startx,$starty,$endx,$endy,$grass,$parking,$handicap,$drawBigImage;
	
	//get start and finish coordinates
	$startx=$_GET["startx"];
	$starty=$_GET["starty"];
	$endx=$_GET["endx"];
	$endy=$_GET["endy"];
	
	//get specified options
	$grass=($_GET["grass"]==1);
	$parking=($_GET["parking"]==1);
	$handicap=($_GET["handicap"]==1);
	
	//gets whether big image should be drawn
	$drawBigImage=toBoolean($_GET['big']);
	
	
		//for testing
		//list($startx,$starty,$endx,$endy,$grass,$parking,$handicap)=array(243,290,436,177,0,0,0);
		
		/*//list($startx,$starty,$endx,$endy)=array(0,0,90,80);//189,20);
		//list($startx,$starty,$endx,$endy)=array(240,159,71,73);//189,20);
		//list($startx,$starty,$endx,$endy)=array(517,204,557,249);
		//list($startx,$starty,$endx,$endy)=array(489,268,238,286);
		list($startx,$starty,$endx,$endy)=array(517,34,436,177);//language bldg to admin bldg
		//list($startx,$starty,$endx,$endy)=array(376,310,371,39);

		list($grass,$parking,$handicap)=array(false,false,false);*/
}

//make 2-D array with which pixels are white or black
function makeArray()
{
	global $map,$width,$height,$grass,$parking,$handicap,		$mapTime;
	
	//get width and height
	$imgPath="../img/algorithm/Sidewalks-crosswalks-bw.png";
	list($width,$height,$type,$attr)=getimagesize($imgPath);
	
		$startTime=microtime(true);
	
	//finds black (blocked) pixels
	$map=array();
	
	fillMap();
	
	//---------------will need to be properly ordered...
	includePaths("../img/algorithm/Sidewalks-crosswalks-bw.png");
	
	if($grass)
	{
		includePaths("../img/algorithm/Grass-bw.png");
	}
	if($parking)
	{
		includePaths("../img/algorithm/Parking-bw.png");
	}
	if($handicap)
	{
		excludePaths("../img/algorithm/Stairs-bw.png");
	}
	
	//excludePaths("../img/algorithm/Buildings-bw.png");//some overhangs in Buildings.png (but overhangs are "pass-able")
	excludePaths("../img/algorithm/Fences-bw.png");
	excludePaths("../img/algorithm/Steep hills-bw.png");
	
		$mapTime=microtime(true)-$startTime;
}

function fillMap()
{
	global $map,$width,$height;
	
	for($x=0; $x<$width; $x++)
	{
		$map[$x]=array_fill(0,$width,1);//faster
	}
}

//includes black pixels as "passable" (e.g. sidewalks=black)
function includePaths($imgPath)
{
	global $map,$width,$height;
	
	$img=imagecreatefrompng($imgPath);
	
	for($x=0; $x<$width; $x++)
	{
		for($y=0; $y<$height; $y++)
		{
			//black = passable
			if((imagecolorat($img,$x,$y) & 0xFF)==0)
			{
				if(isset($map[$x][$y]))//optimization: for speed
				{
					//1=not passable, <unset>=passable
					unset($map[$x][$y]);
				}
			}
		}
	}
	
	//frees memory
	imagedestroy($img);
}

//excludes white pixels => not passable (e.g. buildings)
function excludePaths($imgPath)
{
	global $map,$width,$height;
	
	$img=imagecreatefrompng($imgPath);
	
	for($x=0; $x<$width; $x++)
	{
		for($y=0; $y<$height; $y++)
		{
			//white = not passable
			if((imagecolorat($img,$x,$y) & 0xFF)==0)
			{
				//1=not passable, <unset>=passable
				$map[$x][$y]=1;
			}
		}
	}
	
	//frees memory
	imagedestroy($img);
}

//moves point from blocked location to closest unblocked location
function movePointToUnblocked($pointX,$pointY)
{
	$minDistance=-1;
	$closestPoint=array();
	
	//increasing "manhattan radius"
	for($mradius=1; $minDistance==-1; $mradius+=1)
	{
		//sets boundaries of "sight" from this node
		$xLeft=normalizeX($pointX-$mradius);
		$xRight=normalizeX($pointX+$mradius);
		$yTop=normalizeY($pointY-$mradius);
		$yBottom=normalizeY($pointY+$mradius);
		
		//for each point within $mradius of ($pointX, $pointY)
		for($x=$xLeft; $x<=$xRight; $x++)
		{
			for($y=$yTop; $y<=$yBottom; $y++)
			{
				//point is not blocked
				if(!isBlocked($x,$y))
				{
					$dx=$x-$pointX;
					$dy=$y-$pointY;
					$distance=sqrt($dx*$dx + $dy*$dy);
					
					//breaks record for closest to ($pointX, $pointY)
					if($minDistance==-1 || $distance<$minDistance)
					{
						$minDistance=$distance;
						$closestPoint=array($x,$y);
					}
				}
			}
		}
	}
	
	//return coordinates of closest point
	return $closestPoint;
}

//returns if pixel is by an obstacle (black pixel)
function isByObstacle($x,$y)
{
	/*
	//if touches an obstacle with 1 pixel radius
	for($dx=-1; $dx<=1; $dx++)
	{
		for($dy=-1; $dy<=1; $dy++)
		{
			//if it's not the ($x,$y) pixel
			if($dx!=0 || $dy!=0)
			{
				$xnew=$x+$dx;
				$ynew=$y+$dy;
				
				//<unset>=black, 1=white (pass-able)
				if(isInBounds($xnew,$ynew) && isBlocked($xnew,$ynew))
				{
					return true;
				}
			}
		}
	}*/
	
	/*
	//if on a side, 1 or 2 pixels are blocked (not all 3)
	$countsR=array(0,0,0);//top,middle,bottom
	$countsC=array(0,0,0);//right,center,left
	
	for($dx=-1; $dx<=1; $dx++)
	{
		for($dy=-1; $dy<=1; $dy++)
		{
			//if it's not the ($x,$y) pixel
			if($dx!=0 || $dy!=0)
			{
				$xnew=$x+$dx;
				$ynew=$y+$dy;
				
				//<unset>=black, 1=white (pass-able)
				if(isInBounds($xnew,$ynew) && isBlocked($xnew,$ynew))
				{
					$countsR[$dy+1]++;
					$countsC[$dx+1]++;
				}
			}
		}
	}
	
	for($i=0; $i<3; $i+=2)
	{
		if($countsR[$i]==1 || $countsR[$i]==2 || $countsC[$i]==1 || $countsC[$i]==2)
		{
			return true;
		}
	}
	
	return false;
	*/
	
	//if at corner of a "blocked" pixel
	for($dx=-1; $dx<=1; $dx+=2)
	{
		for($dy=-1; $dy<=1; $dy+=2)
		{
			$xnew=$x+$dx;
			$ynew=$y+$dy;
		
			if(isBlocked($xnew,$ynew)//corner is blocked
				&& !isBlocked($x,$ynew) && !isBlocked($x,$ynew+$dy)
				&& !isBlocked($xnew,$y) && !isBlocked($xnew+$dx,$y))//both adjacent squares are not blocked
			{
				return true;
			}
		}
	}
	
	return false;
}

//returns if coordinate is within map
function isInBounds($x,$y)
{
	global $width,$height;
	
	return ($x>=0 && $x<$width && $y>=0 && $y<$height);
}

//find the shortest path between the points
//according to user-set options
//
//returns true if path between two points exists
function findShortestPath()
{
	global $fScore,$toBeEvaluated,$cameFrom,$width,$height,$startx,$starty,$endx,$endy,$keyNodes,		$pathTime,$subTime,$keyNodesTime;//any other options are also globals
	
		$startTime=microtime(true);
		//$indexed=0;
	
	//radius of "sight" from a node
	$radius=3;//5;//higher radius => higher accuracy & slower results
	
	//init keyNode stuff
	$isNotKeyNode=array();
	$gridSquareLength=2;
	$keyNodes[$startx][$starty]=1;
	$keyNodes[$endx][$endy]=1;
	
	//arrays used for algorithm
	$toBeEvaluated=array(array($startx,$starty));
	$cameFrom=array();
	$state=array();//2=evaluated, 1=toBeEvaluated, <not set>=neither
	
	$fScore=array();
	$gScore=array();
	
	$gScore[$startx][$starty]=0;
	
	//f(x) = g(x) + h(x)
	$fScore[$startx][$starty]=$gScore[$startx][$starty]+distanceBetween($startx,$starty,$endx,$endy);
	
	//while $toBeEvaluated is not empty
	while(!empty($toBeEvaluated))
	{
		//node within $toBeEvaluated with lowest fScore
		$current=spliceNodeWithLowestFScore();
		$currentX=$current[0];
		$currentY=$current[1];//echo("$currentX , $currentY \n");
		//list($currentX,$currentY)=$current;//same performance
		
		//if at end
		if($currentX==$endx && $currentY==$endy)
		{
			//echo("finished!<br>\n");// indexed: $indexed \n");
			
				$pathTime=microtime(true)-$startTime;
			
			//collapses path
			collapsePath();
			
			return true;
		}
		
		//sets $state to 'evaluated' for this node
		$state[$currentX][$currentY]=2;
		
		//sets boundaries of "sight" from this node
		$xLeft=normalizeX($currentX-$radius);
		$xRight=normalizeX($currentX+$radius);
		$yTop=normalizeY($currentY-$radius);
		$yBottom=normalizeY($currentY+$radius);
		
		//for each neighbor of $current node
		for($x=$xLeft; $x<=$xRight; $x++)
		{
			for($y=$yTop; $y<=$yBottom; $y++)
			{
					$subStart=microtime(true);
					
				$isKeyNode=isset($keyNodes[$x][$y]);
				
				//not checked
				if(!$isKeyNode && !isset($isNotKeyNode[$x][$y]))
				{
					//is a key node
					if(!isBlocked($x,$y) && (($x%$gridSquareLength==0 && $y%$gridSquareLength==0) || isByObstacle($x,$y)))
					{
						$keyNodes[$x][$y]=1;
						$isKeyNode=true;
							//$indexed++;
					}
					//is not a key node
					else
					{
						$isNotKeyNode[$x][$y]=1;
							//$indexed++;
					}
				}
				
					$keyNodesTime+=(microtime(true)-$subStart);
				
				//is a "key node", and is NOT blocked (black pixel), and the 2 points are "neighbors"
				if($isKeyNode /*isset($keyNodes[$x][$y])*/ /*&& !isBlocked($x,$y) not needed b/c keyNodes are always "pass-able" */ && neighbors($currentX,$currentY,$x,$y))
				{
					$neighbor=array($x,$y);
					
					//if NOT already evaluated this neighbor
					if(!isset($state[$x][$y]) || $state[$x][$y]!=2)
					{
						$tentative_gScore=$gScore[$currentX][$currentY]+distanceBetween($currentX,$currentY,$x,$y);
						
						$inToBeEvaluated=(isset($state[$x][$y]) && $state[$x][$y]==1);
						
						//if neighbor NOT in $toBeEvaluated or $tentative_gScore < gScore of neighbor
						if(!$inToBeEvaluated || $tentative_gScore<$gScore[$x][$y])
						{
							//if neighbor not in $toBeEvaluated
							if(!$inToBeEvaluated)
							{
								//adds neighbor to $toBeEvaluated
								$toBeEvaluated[]=$neighbor;
								
								//sets $state for this node
								$state[$x][$y]=1;
							}
							
							$cameFrom[$x][$y]=array($currentX,$currentY);
							$gScore[$x][$y]=$tentative_gScore;
							
							//f(x) = g(x) + h(x)
							$fScore[$x][$y]=$tentative_gScore+distanceBetween($x,$y,$endx,$endy);
						}
					}
				}
					
					$subTime+=(microtime(true)-$subStart);
			}
		}//end double-for
		
		//get rid of unneeded f,g scores
		//unset($fScore[$currentX][$currentY]);
		//unset($gScore[$currentX][$currentY]);//leads to slightly longer runtime
		
	}//end while
	
		$pathTime=microtime(true)-$startTime;
	
	//could NOT find a path to finish
	return false;
}

//normalize X based on image width
function normalizeX($x)
{
	global $width;
	
	if($x<0)
	{
		return 0;
	}
	else if($x>=$width)
	{
		return $width-1;
	}
	
	return $x;
}

//normalize Y based on image height
function normalizeY($y)
{
	global $height;
	
	if($y<0)
	{
		return 0;
	}
	else if($y>=$height)
	{
		return $height-1;
	}
	
	return $y;
}

//if a pixel is blocked
function isBlocked($x,$y)
{
	global $map;
	
	return (isset($map[$x][$y]));
}

//removes and returns the coordinates of node in $toBeEvaluated with the lowest f_score
function spliceNodeWithLowestFScore()
{
	global $fScore,$toBeEvaluated	,$lowFTime;
	
		$startTime=microtime(true);
	
	$lowestFScore=-1;
	$lowestIndex=-1;
	
	foreach($toBeEvaluated as $key => $point)
	{
		$x=$point[0];
		$y=$point[1];
		$pointFScore=$fScore[$x][$y];
		
		if($lowestFScore==-1 || $pointFScore<$lowestFScore)
		{
			$lowestFScore=$pointFScore;
			$lowestIndex=$key;
		}
	}
	
	//error
	if($lowestIndex==-1)
	{
		echo("error: lowestIndex == -1<br>\n");
	}
	
		$lowFTime+=(microtime(true)-$startTime);
	
	$node=$toBeEvaluated[$lowestIndex];
	unset($toBeEvaluated[$lowestIndex]);
	
	return $node;
}

//returns distance between points
function distanceBetween($ax,$ay,$bx,$by)
{
		global $distanceBetweenTime;
		$startTime=microtime(true);
	
	//displacement distances (x, y, and hypotenuse)
	$x=$bx-$ax;
	$y=$by-$ay;
	$dist=sqrt($x*$x + $y*$y);
	
		$distanceBetweenTime+=(microtime(true)-$startTime);
	
	return $dist;
}

//returns true if two points make unblocked line
function neighbors($ax,$ay,$bx,$by)
{
		global $neighborsTime;
	
	//both points are the same point
	if($ax==$bx && $ay==$by)
	{
		return false;
	}
	
		$startTime=microtime(true);
	
	//displacement distances (x, y, and hypotenuse)
	$x=$bx-$ax;
	$y=$by-$ay;
	$h=sqrt($x*$x + $y*$y);
	
	//"small" displacement distances
	$dh=.8;
	$dx=$dh*$x/$h;
	$dy=$dh*$y/$h;
	
	//travelling point: $tx, $ty
	$tx=$ax+$dx;
	$ty=$ay+$dy;
	
	//max number of steps
	$maxSteps=($h/$dh)-1;
	
	//travelling
	for($steps=0; $steps<$maxSteps; $steps++)
	{
		if(isBlocked(floor($tx),floor($ty)))
		{
			return false;
		}
		
		$tx+=$dx;
		$ty+=$dy;
	}
	
	if(isBlocked($bx,$by))
	{
		return false;
	}
	
		$neighborsTime+=(microtime(true)-$startTime);
	
	return true;
}

//collapses path to shortest possible route between points
function collapsePath()
{
	global $cameFrom,$startx,$starty,$endx,$endy,		$collapseTime;
	
		$startTime=microtime(true);
	
	//A = node of focus
	$ax=$endx;
	$ay=$endy;
	
	//starts at finish and goes through until arriving at start
	while(!($ax==$startx && $ay==$starty))
	{
		//gets A's predecessor
		$b=$cameFrom[$ax][$ay];
		$bx=$b[0];
		$by=$b[1];
		
		$lastNeighboringA=$b;
		
		if(isset($cameFrom[$bx][$by]))
		{
			//gets predecessor's predecessor
			$b=$cameFrom[$bx][$by];
			$bx=$b[0];
			$by=$b[1];
			
			//cycle through previous nodes, stopping at furthest node that is neighbors with node A
			while(neighbors($ax,$ay,$bx,$by) && isset($cameFrom[$bx][$by]))
			{
				$lastNeighboringA=$b;
				
				$b=$cameFrom[$bx][$by];
				$bx=$b[0];
				$by=$b[1];
			}
		}
		
		
		
		//if there's a node before A's predecessor that is neighbors with A
		if($lastNeighboringA!=$cameFrom[$ax][$ay])
		{
			//collapse A to lastNeighboringA
			$cameFrom[$ax][$ay]=$lastNeighboringA;
		}
		
		//proceed to try to collapse from lastNeighboringA
		$ax=$lastNeighboringA[0];
		$ay=$lastNeighboringA[1];
	}
	
		$collapseTime=microtime(true)-$startTime;
}

//generates output and image
function generateOutput()
{
	global $startx,$starty,$endx,$endy,$grass,$parking,$handicap,$drawBigImage,		$outputTime;
	
		$startTime=microtime(true);
	
	//get filepath for output image
	$imgPath=getImagePath();
	$bigImagePath=getImageBigPath();
	
	generateImage('../'.$imgPath,'../'.$bigImagePath, $distance);
	
	$outputImagePath=($drawBigImage)?getImageBigPath():$imgPath;//whether 600 or 2500-width image
	writeData($distance,$outputImagePath);
	
		//for debugging
		echo("\n".'<br><a href="../'.$outputImagePath.'">view the generated image</a>');
		
		$outputTime+=(microtime(true)-$startTime);
}

//returns true=>1, false=>0
function toBinary($bool)
{
	return $bool?1:0;
}

function toBoolean($binary)
{
	return ($binary==1);
}

//reconstructs path from finish to start
//and creates image from this
function generateImage($imgPath,$bigImagePath, &$distance)
{
	global $cameFrom,$startx,$starty,$endx,$endy,$drawBigImage,$bigWidth,$bigHeight;
	
	//the color map
	$img=imagecreatefrompng('../img/maps/map600.png');
	if($drawBigImage)
	{
		$bigImage=imagecreatefrompng('../img/maps/map2500.png');//2500-width
		$scaleFactor=2500/600;
		
		//gets width, height of bigImage
		list($bigWidth,$bigHeight,$type,$attr)=getimagesize('../img/maps/map2500.png');
	}
	
	//the path to be drawn
	$pathColor=imagecolorallocate($img,255,0,0);
	$brushRadius=1;
	$bigBrushRadius=3;
	
	//resets $distance
	$distance=0;
	
	$point=array($endx,$endy);
	$startPoint=array($startx,$starty);
	
	//travels along path, coloring the trail
	while($point!=$startPoint)
	{
		$ax=$point[0];
		$ay=$point[1];
		
		//saves new $point
		$point=$cameFrom[$ax][$ay];
		
		$bx=$point[0];
		$by=$point[1];
		
		//displacement distances (x, y, and hypotenuse)
		$x=$bx-$ax;
		$y=$by-$ay;
		$h=sqrt($x*$x + $y*$y);
		$distance+=$h;
		
		//"small" displacement distances
		$dh=1;//0.7;
		$dx=$dh*$x/$h;
		$dy=$dh*$y/$h;
		
		//travelling point: $tx, $ty
		$tx=$ax;
		$ty=$ay;
		
		//max number of steps
		$maxSteps=$h/$dh;
		
		//scaled dx,dy,tx,ty
		if($drawBigImage)
		{
			$bigdx=$dx*$scaleFactor;
			$bigdy=$dy*$scaleFactor;
			$bigtx=($ax*$scaleFactor)+2;//+2 to be in middle of all points which map to 
			$bigty=($ay*$scaleFactor)+2;//that point on map600 (due to scaling)
		}
		
		
		
		//travelling (for 600-width image)
		for($steps=0; $steps<$maxSteps; $steps++)
		{
			brushPixel($img,false,$tx,$ty,$pathColor,$brushRadius);
			$tx+=$dx;
			$ty+=$dy;
		}
		
		brushPixel($img,false,$bx,$by,$pathColor,$brushRadius);
		
		
		
		//if drawing 2500-width image
		if($drawBigImage)
		{
			for($steps=0; $steps<$maxSteps; $steps++)
			{
				brushPixel($bigImage,true,$bigtx,$bigty,$pathColor,$bigBrushRadius);				
				$bigtx+=$bigdx;
				$bigty+=$bigdy;
			}
			
			brushPixel($bigImage,true,$bx*$scaleFactor+2,$by*$scaleFactor+2,$pathColor,$bigBrushRadius);
		}
	}
	
	//scales $distance
	$distance*=0.0015625;
	//(0.5 mi / 320 pixels) = 0.0015625 mi/pixels
	
	//encodes image with distance, saves image to file
	encodeIntoImage($img,''.$distance);
	imagepng($img,$imgPath);
	imagedestroy($img);
	
	if($drawBigImage)
	{
		imagepng($bigImage,$bigImagePath);
		imagedestroy($bigImage);
	}
	
		//echo("@ start :: $startx , $starty<br>\n");
}

//'brushes' pixel with a radius, r
function brushPixel(&$img,$isBigImage,$currentX,$currentY,&$pathColor,$radius)
{
	if($isBigImage)
	{
		$xLeft=normalizeBigX($currentX-$radius);
		$xRight=normalizeBigX($currentX+$radius);
		$yTop=normalizeBigY($currentY-$radius);
		$yBottom=normalizeBigY($currentY+$radius);
	}
	//normal-sized image
	else
	{
		//sets boundaries of "sight" from this node
		$xLeft=normalizeX($currentX-$radius);
		$xRight=normalizeX($currentX+$radius);
		$yTop=normalizeY($currentY-$radius);
		$yBottom=normalizeY($currentY+$radius);
	}
	
	//for each neighbor of $current node
	for($x=$xLeft; $x<=$xRight; $x++)
	{
		for($y=$yTop; $y<=$yBottom; $y++)
		{
			imagesetpixel($img,round($x),round($y),$pathColor);
		}
	}
}

//normalize X based on image width
function normalizeBigX($x)
{
	global $bigWidth;
	
	if($x<0)
	{
		return 0;
	}
	else if($x>=$bigWidth)
	{
		return $bigWidth-1;
	}
	
	return $x;
}

//normalize Y based on image height
function normalizeBigY($y)
{
	global $bigHeight;
	
	if($y<0)
	{
		return 0;
	}
	else if($y>=$bigHeight)
	{
		return $bigHeight-1;
	}
	
	return $y;
}

//encodes $str into $img
function encodeIntoImage(&$img,$str)
{
	//number of characters to encode into $img
	$maxChars=9;//max maxChars=9
	$strLength=strlen($str);
	$numChars=($strLength>$maxChars)?$maxChars:$strLength;
	
	//encodes $numChars into $img, row=0
	encodeCharToRow($img,$numChars,0);
	
	//encodes each char row-by-row
	for($row=1; $row<=$numChars; $row++)
	{
		$char=substr($str,$row-1,1);
		encodeCharToRow($img,$char,$row);
	}
}

//encodes a char into specified row in $img
function encodeCharToRow(&$img,$char,$row)
{
	$ascii=ord($char);
	
	for($x=0; $x<8; $x++)
	{
		$oldColor=imagecolorat($img,$x,$row);
		
		//gets next bit of $ascii
		$asciiBit=($ascii & 1);
		
		//sets pixel to (possibly) new color
		$newColor=($oldColor - ($oldColor & 1))+$asciiBit;
		imagesetpixel($img,$x,$row,$newColor);
		
		$ascii=$ascii>>1;
	}
}

//echo JSON object with distance, imageURL
function writeData($distance,$imageURL)
{
	echo('{"distance":"'.$distance.'", "imageURL":"'.$imageURL.'"}');
}

//returns suppose`d image path
function getImagePath()
{
	global $startx,$starty,$endx,$endy,$grass,$parking,$handicap;
	
	return 'usr/img-'.$startx.'_'.$starty.'-'.$endx.'_'.$endy.'-'.toBinary($grass).toBinary($parking).toBinary($handicap).'.png';
}

//returns suppose`d image path
function getImageBigPath()
{
	global $startx,$starty,$endx,$endy,$grass,$parking,$handicap;
	
	return 'usr/img-'.$startx.'_'.$starty.'-'.$endx.'_'.$endy.'-'.toBinary($grass).toBinary($parking).toBinary($handicap).'-big.png';
}



//
// decoding from cache functionality
//

//returns if this path has been generated
function isPathCached()
{
	global $drawBigImage;
	
	$imgPath=getImagePath();
	
	//only need 600-width image
	if(!$drawBigImage)
	{
		//image must exist
		return file_exists('../'.$imgPath);
	}
	//need 2500-width image
	else
	{
		$bigImagePath=getImageBigPath();
		
		//both 600 and 2500 width images must exist
		return file_exists('../'.$imgPath) && file_exists('../'.$bigImagePath);
	}
}

//retrieves output, given this path has already been generated
function retrieveOutput()
{
	global $startx,$starty,$endx,$endy,$grass,$parking,$handicap,$drawBigImage,		$outputTime;
	
		$startTime=microtime(true);
	
	//decodes $distance from $img
	$imgPath=getImagePath();
	$img=imagecreatefrompng('../'.$imgPath);
	$distance=decodeFromImage($img);
	imagedestroy($img);
	
	//writes distance and image's path
	$outputImagePath=($drawBigImage)?getImageBigPath():$imgPath;//whether 600 or 2500-width image
	writeData($distance,$outputImagePath);
	
		//for debugging
		echo("\n".'<br><a href="../'.$outputImagePath.'">view the generated image</a>');
		
		$outputTime+=(microtime(true)-$startTime);
}

//decodes $str from $img
function decodeFromImage(&$img)
{
	//number of characters to decode from $img
	$numChars=decodeCharFromRow($img,0);
	$str='';
	
	//decodes each char row-by-row
	for($row=1; $row<=$numChars; $row++)
	{
		$char=decodeCharFromRow($img,$row);
		$str.=$char;
	}
	
	return $str;
}

//decodes a char from specified row in $img
function decodeCharFromRow(&$img,$row)
{
	$asciiBinary='';
	
	for($x=0; $x<8; $x++)
	{
		$color=imagecolorat($img,$x,$row);
		$asciiBinary=($color & 1).$asciiBinary;
	}
	
	$ascii=bindec($asciiBinary);
	
	return chr($ascii);
}

?>
